public class SplayTree<T extends Comparable<T>> {

    public SplayTreeNode<T> getRoot() {
        return mRoot;
    }

    public class SplayTreeNode<T>{
        public T key;
        SplayTreeNode<T> left;
        SplayTreeNode<T> right;

        public SplayTreeNode(T key, SplayTreeNode<T> left, SplayTreeNode<T> right) {
            this.key = key;
            this.left = left;
            this.right = right;
        }

        public SplayTreeNode(T key) {
            this.key = key;
        }
    }

    private SplayTreeNode mRoot;

/**
 * 比较--->查找目标节点--->对目标节点的父节点进行旋转。
 * */
    public SplayTreeNode<T> splay(SplayTreeNode<T> tree,T data){
        if(tree == null)
            return null;
        int cmp = data.compareTo(tree.key);
        //小于0,说明目标节点在左子树
        if(cmp<0){
            tree.left = splay(tree.left,data);
            tree = rotationRight(tree);
        }else if(cmp>0){
            tree.right = splay(tree.right,data);
            tree = rotationLeft(tree);
        }else{
            return tree;
        }
        return tree;
    }

    private SplayTreeNode<T> rotationLeft(SplayTreeNode<T> root){
        SplayTreeNode<T> newRoot = root.right;
        root.right = newRoot.left;
        newRoot.left = root;
        return newRoot;

    }

    private SplayTreeNode<T> rotationRight(SplayTreeNode<T> root){
        SplayTreeNode<T> newRoot = root.left;
        root.left = newRoot.right;
        newRoot.right = root;
        return newRoot;

    }

    public SplayTreeNode<T> search(T data){
        return search(mRoot,data);
    }

    private SplayTreeNode<T> search(SplayTreeNode<T> tree,T data){
        if(tree == null)
            return null;
        int cmp = data.compareTo(tree.key);
        if(cmp<0){
            return search(tree.left,data);
        }else if(cmp>0){
            return search(tree.right,data);
        }else{
            mRoot = splay(mRoot,data);
            return tree;
        }
    }

    private SplayTreeNode<T> insert(SplayTreeNode<T> tree,T data){
        if(tree == null)
            return new SplayTreeNode<T>(data);
        int cmp = data.compareTo(tree.key);
        if(cmp<0){
            tree.left = insert(tree.left,data);
            tree = splay(tree,data);
        }else if(cmp>0){
            tree.right = insert(tree.right,data);
            tree = splay(tree,data);
        }else{
            System.out.println("已经存在了该值");
            return null;
        }
        return tree;
    }

    public SplayTreeNode<T> insert(T data){
        mRoot = insert(mRoot,data);
        //mRoot = splay(mRoot,data);
        return mRoot;
    }

    /**
     * 删除时，进行伸展
     * a,找到删除的节点
     * b,对删除的节点进行旋转，使它成为根节点。
     * c,删除该节点后，问题是如何将左右子树进行拼接
     * 1),若左子树不为空，则找到左子树中的最大值，因为左子树的最大节点没有右子树
     * 1.1),将选中的最大值节点进行旋转，使其成为根节点。
     * 1.2),将原来的右子树拼接过来
     * 2),若左子树为空，则右子树直接成为完整的树。
     * */
    public SplayTreeNode<T> remove(T data){
         SplayTreeNode<T> newRoot,removeRoot;
         if(mRoot == null)
             return null;
         removeRoot = search(mRoot,data);
         
         if(removeRoot == null)
             return null;
         mRoot = splay(mRoot,data);
         
         if(mRoot.left!=null){
             newRoot = splay(mRoot.left,(T)findMax(mRoot.left).key);
             newRoot.right = mRoot.right;
         }else{
             newRoot = mRoot.right;
         }

         mRoot = newRoot;
         return removeRoot;
    }

    private SplayTreeNode<T> findMax(SplayTreeNode<T> tree) {
        if (tree == null){
            return null;
        }
        while(tree.right!=null){
            tree = tree.right;
        }
        return tree;
    }

    private void inOrder(SplayTreeNode<T> tree){
        if(tree!=null){
            inOrder(tree.left);
            System.out.println(tree.key+" ");
            inOrder(tree.right);
        }
    }

    public void inOrder(){
        inOrder(mRoot);
    }

    private void preOrder(SplayTreeNode<T> tree){
        if(tree!=null){
            System.out.println(tree.key+" ");
            preOrder(tree.left);
            preOrder(tree.right);
        }
    }

    public void preOrder(){
        preOrder(mRoot);
    }

    private void postOrder(SplayTreeNode<T> tree){
        if(tree!=null){
            postOrder(tree.left);
            postOrder(tree.right);
            System.out.println(tree.key+" ");
        }
    }

    public void postOrder(){
        postOrder(mRoot);
    }


}
